package com.extra;

public class Solution143 {
    public void reorderList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode p = null;
        ListNode q;
        while (tmp != null) {
            q = tmp.next;
            tmp.next = p;
            p = tmp;
            tmp = q;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int flag = 0;
        while (p != null && head != null) {
            if (flag % 2 == 0) {
                cur.next = head;
                head = head.next;
            } else {
                cur.next = p;
                p = p.next;
            }
            flag++;
            cur = cur.next;
        }
        if (head != null) cur.next = head;
        if (p != null) cur.next = p;
        head = dummy.next;
    }
}
